מכרז Vickrey-Clarke-Groves

מכרז Vickrey–Clarke–Groves הוא סוג של מכירה פומבית סגורה המציעה לקונים מספר פריטים וכל קונה מגיש הצעת מחיר שונה לכל פריט. במכירה זו כל פריט מוקצה בצורה האופטימלית החברתית וכל קונה זוכה לכל היותר בפריט אחד. במנגנון זה כל קונה משלם את הנזק שהוא גורם לקונים האחרים ובכך מובטח שהאסטרטגיה הטובה ביותר עבור הקונה היא להציע את המחיר האמיתי שהקונה מעדיף לשלם עבור כל פריט ופריט. מנגנון זה הוא הכללה של מכרז מחיר שני עבור מספר רב של פריטים.

הגדרה פורמלית

תהי $M=\{t_{1},\ldots ,t_{m}\}$ קבוצת הפריטים המוצעים למכירה, ותהי $N=\{b_{1},\ldots ,b_{n}\}$ קבוצת הקונים במכירה. נגדיר גם את $V_{N}^{M}$ כערך הפונקציה החברתית המתקבל במנגנון המכירה עם קבוצת הפריטים $M$ וקבוצת הקונים $N$ לאחר שאלו הגישו את הצעותיהם.

אם הקונה $b_{i}$ זוכה בפריט $t_{j}$ אז המחיר שעליו לשלם לפי מנגנון VCG מוגדר להיות $V_{N\setminus \{b_{i}\}}^{M}-V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}$. הביטוי הראשון הוא ערך הפונקציה החברתית שמתקבל כאשר הקונה $b_{i}$ אינו משתתף במכירה, הביטוי השני הוא ערך הפונקציה החברתית כאשר גם הקונה וגם הפריט $t_{j}$ אינם משתתפים במכירה. כלומר, הביטוי השני הוא הערך המתקבל מכל שאר המשתתפים במכירה כאשר $b_{i}$ השתתף במכירה והביטוי הראשון הוא הערך המתקבל מכל שאר המשתתפים במכירה כאשר $b_{i}$ לא השתתף במכירה. לכן ההפרש ביניהם הוא הנזק ש$b_{i}$ גורם לשאר הקונים.

על סמך ההגדרות הנ"ל, אם הערך האמיתי של הפריט $t_{j}$ בעיני הקונה $b_{i}$ הוא $A$, אז התועלת המתקבלת לקונה $b_{i}$ במכירה היא $A-\left(V_{N\setminus \{b_{i}\}}^{M}-V_{N\setminus \{b_{i}\}}^{M\setminus \{t_{j}\}}\right)$ (הערך שהקונה מרוויח מהפריט פחות התשלום על הנזק שנגרם לשאר הקונים).

דוגמה

נניח שבמכירה מוצעים שני תפוחים וקיימים שלושה קונים. קונה א' רוצה תפוח אחד ומציע עבורו 5 ש"ח. קונה ב' מעוניין גם בתפוח אחד ומוכן לשלם עבורו 2 ש"ח. קונה ג' רוצה שני תפוחים ומוכן לשלם 6 ש"ח עבור שניהם בתנאי שהוא זוכה בשניהם (ולא בתפוח אחד בלבד). תחילה, נעריך את תוצאת המכירה כשבוחרים בהצעות היקרות ביותר לכל פריט: קונה א' וקונה ב' זוכים כל אחד בתפוח אחד. כעת, כדי לחשב את התשלומים שעליהם לשלם עבור הנזקים שגרמו לקונים האחרים, נחשב את השפעת ההצעה על שאר הקונים. לפי התוצאה כרגע, התועלת של לקוח ב' היא 2 ש"ח. נניח ולקוח א' לא היה משתתף במכרז, לקוח ג' היה זוכה עם תועלת של 6 ש"ח ולכן לקוח א' משלם 6-2=4 ש"ח. בעבור לקוח ב': התועלת של לקוח א' כרגע היא 5 ש"ח והתועלת של לקוח ג' היא 0, נניח ולקוח ב' לא היה משתתף במכרז, לקוח ג' היה זוכה עם תועלת של 6 ש"ח ולכן לקוח ב' משלם 6-5=1 ש"ח. התוצאה הייתה זהה אם לקוח ג' לא היה משתתף ולכן הוא אינו חייב לשלם דבר.

הוכחת האופטימליות של אמירת האמת

נבחר קונה אחד באופן שרירותי $b_{1}$ ונתמקד בו. יהי $v_{i}$ הערך האמיתי שהקונה מציעה לפריט $t_{i}$. נניח, בה"כ, שאם $b_{1}$ מציע את הערכותיו האמיתיות, מנגנון VCG מקצה לו את פריט $t_{1}$. נשים לב תחילה שלהצעותיו של $b_{1}$ אין השפעה על ערך התועלת שלו, בהנחה שהוא זוכה באותו פריט, מכיוון שהתועלת של $b_{1}$ בלתי תלויה בערכים האחרים.

נניח ש$b_{1}$ אינו מציע את הערכותיו האמיתיות וזוכה בפריט $t_{j}$ בזכות הצעותיו המטעות. במקרה שהיה מגיש את הערכותיו האמיתיות התועלת של $b_{1}$ היא $U_{1}=v_{1}-\left(V_{N\setminus \{b_{1}\}}^{M}-V_{N\setminus \{b_{1}\}}^{M\setminus \{t_{1}\}}\right)$. במקרה שהציע את הערכותיו המטעות התועלת היא $U_{2}=v_{j}-\left(V_{N\setminus \{b_{1}\}}^{M}-V_{N\setminus \{b_{1}\}}^{M\setminus \{t_{j}\}}\right)$. צריך להוכיח ש $U_{1}-U_{2}\geq 0$, כלומר התועלת של הצעת אמת עולה על התועלת של הצעה מטעה.

$U_{1}-U_{2}=v_{1}-\left(V_{N\setminus \{b_{1}\}}^{M}-V_{N\setminus \{b_{1}\}}^{M\setminus \{t_{1}\}}\right)-v_{j}+\left(V_{N\setminus \{b_{1}\}}^{M}-V_{N\setminus \{b_{1}\}}^{M\setminus \{t_{j}\}}\right)=\left[v_{1}+V_{N\setminus \{b_{1}\}}^{M\setminus \{t_{1}\}}\right]-\left[v_{j}+V_{N\setminus \{b_{1}\}}^{M\setminus \{t_{j}\}}\right]$

הביטוי הראשון הוא הערך המקסימלי המתקבל של פונקציית התועלת החברתית כש $b_{1}$ זכה בפריט $t_{1}$. הביטוי השני הוא הערך המקסימלי של פונקציית התועלת החברתית כש $b_{1}$ זכה בפריט $t_{j}$. מכיוון שאנחנו מניחים שמנגנון VCG הקצה ל$b_{1}$ את הפריט $t_{1}$ אז הערך של הביטוי הראשון הוא הגדול יותר ולכן מתקבל $U_{1}-U_{2}\geq 0$.

מקרה כללי יותר

ישנה הבחנה כללית יותר למנגנון VCG. נתבונן בקבוצה $A$ היא קבוצת התוצאות האפשריות של $n$ קונים המציעים ערכים שונים לכל תוצאה. ניתן לבטא זאת כפונקציה:

$v_{i}:A\longrightarrow R_{+}$

המבטאת לכל קונה $i$ את הערך שנתן לכל תוצאה אפשרית. במכרז זה, כל קונה מציע את הערכותיו שלו ומנגנון VCG בוחר את האפשרות $a\in A$ שממקסמת את $\sum _{i}v_{i}(a)$ וגובה מחיר $p_{i}$ המוגדר באופן הבא:

$p_{i}=h_{i}(v_{-i})-\sum _{j\neq i}v_{j}(a)$

כאשר $v_{-i}=(v_{1},\dots ,v_{i-1},v_{i+1},\dots ,v_{n})$. כלומר $h_{i}$ היא פונקציה התלויה רק בהצעות של הקונים האחרים. תנאי זה מספיק להבטיח אמירת אמת כאסטרטגיה שלטת

אפשר לקחת, לדוגמה, $h_{i}(v_{-i})=0$ אבל אז כל המחירים המתקבלים יהיו שליליים. באופן כללי במכירות אנחנו מעדיפים שהלקוחות ישלמו מאשר שהמכרז ישלם לקונים. הפונקציה:

$h_{i}(v_{-i})=\max _{b\in A}\sum _{j\neq i}v_{j}(b)$

נקראת Clarke pivot rule. ויש לה שתי תכונות מעניינות:

• היא מועילה לכל קונה בנפרד. $v_{i}(a)-p_{i}\geq 0$ כל קונה המשתתף במכרז מקבל תועלת חיובית, אף אחד לא חייב להציע הצעה.

• היא מועילה למנהלי המכרז. $p_{i}\geq 0$. המנגנון לא משלם דבר לקונים.